#include "LinkTree.h"
#include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
    TreeElementType data;
    struct TreeNode* parent;
    DLlist childs;
};

struct LinkTree
{
    TNode *root;
};

TNode *CreateTreeNode(TreeElementType element)
{
    TNode *node = (TNode*)malloc(sizeof(TNode));
    if(node == NULL)
    {
        printf("create node error!\n");
        return NULL;
    }

    node->data = element;
    node->parent = NULL;
    InitDLlist(&node->childs);
    return node;
}

void *GetTreeNodeData(TNode *node)
{
    return node->data;
}

void ConnectBranch(TNode *parent, TNode *child)
{
    if(parent == NULL || child == NULL)
        return;
    
    child->parent = parent;
    InsertTail1(&parent->childs,child);
}

bool IsNodeEqual(void *ptr1,void *ptr2)
{
    TNode *s1 = (TNode*)ptr1;
    TNode *s2 = (TNode*)ptr2;
    return s1 == s2;
}

void DisconnectBranch(TNode *parent, TNode *child)
{
    if(parent == NULL || child == NULL)
        return;

    if(child->parent != parent)
    {
        printf("两者不是父子关系!\n");
        return;
    }
    
    child->parent = NULL;
    RemoveByElement(&parent->childs,child,IsNodeEqual,NULL);
}


TNode *FindChildNode(TNode *parent, void *value, bool (*funcPtr)(void *, void *))
{
    DLNode *TravelPoint = parent->childs.head;
    while(TravelPoint->next != NULL)
    {
        TNode *child = (TNode*)TravelPoint->next->data;
        if(funcPtr(child->data,value) == true)
        {
            return child;
        }
        TravelPoint = TravelPoint->next;
    }
    return NULL;
}

void FreeTreeNode(void *node)
{
    TNode *freeNode = (TNode*)node;
    if(freeNode == NULL)
        return;
    ClearDLlist(&freeNode->childs,FreeTreeNode);
    free(freeNode);
}

LTree *InitLinkTree()
{
    LTree *tree = (LTree*)malloc(sizeof(LTree));
    if(tree == NULL)
        return NULL;
    
    tree->root = CreateTreeNode(NULL);
    return tree;
}

TNode *GetTreeRoot(LTree *tree)
{
    return tree->root;
}

int GetTreeNodeHeight(TNode *node)
{
    if(node == NULL)
        return 0;
    
    DLNode *TravelPoint = node->childs.head;
    int height = 0;
    while(TravelPoint->next != NULL)
    {
        int childHeight = GetTreeNodeHeight((TNode*)TravelPoint->next->data);
        height = height > childHeight ? height : childHeight;
        TravelPoint = TravelPoint->next;
    }
    return height + 1;
}

int GetTreeHeight(LTree *tree)
{
    return GetTreeNodeHeight(tree->root) - 1;
}

void TravelTreeNode(TNode *node,int deepth,void(*funcPtr)(void*))
{
    if(node == NULL || funcPtr == NULL)
        return;
    
    if(node->parent != NULL)
    {
        for(int i = 0; i < deepth; i++)
            printf("    ");
        if(deepth >= 1)
            printf("|__");
        funcPtr(node->data);
    }

    DLNode *TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        TravelTreeNode((TNode*)TravelPoint->next->data,deepth + 1,funcPtr);
        TravelPoint = TravelPoint->next;
    }
}

void TravelTree(LTree *tree, void (*funcPtr)(void *))
{
    TravelTreeNode(tree->root,-1,funcPtr);
}

TNode *FindTreeNode(TNode *node,void *value,bool(*funcPtr)(void *,void *))
{
    if(node == NULL || funcPtr == NULL)
        return NULL;
    if(node->parent != NULL && funcPtr(node->data,value) == true)
    {
        return node;
    }

    TNode *targetNode = NULL;
    DLNode *TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        targetNode = FindTreeNode((TNode*)TravelPoint->next->data,value,funcPtr);
        if(targetNode != NULL)
        {
            return targetNode;
        }
        TravelPoint = TravelPoint->next;
    }
    return targetNode;
}

TNode *FindLinkTreeNode(LTree *tree, void *value, bool (*funcPtr)(void *, void *))
{
    return FindTreeNode(tree->root,value,funcPtr);
}

void FindAllLeaves(TNode *node,DLlist *list)
{
    if(node == NULL)
        return;
    if(node->childs.len == 0)
    {
        InsertTail1(list,node);
    }

    DLNode *TravelPoint = node->childs.head;
    while(TravelPoint->next != NULL)
    {
        FindAllLeaves((TNode*)TravelPoint->next->data,list);
        TravelPoint = TravelPoint->next;
    }
}

DLlist FindAllLeafBranch(LTree *tree)
{
    DLlist list;
    InitDLlist(&list);
    FindAllLeaves(tree->root,&list);
    return list;
}

void ClearLinkTree(void *tree)
{
    if(tree == NULL)
        return;
    
    LTree *tp = (LTree*)tree;
    FreeTreeNode(tp->root);
    free(tp);
}
